// 227.基本计算器2
package Leetcode_Second_Brush;

import java.util.Deque;
import java.util.LinkedList;

public class Solution227 {
    public int calculate(String s) {
        Deque<Integer> nums = new LinkedList<>();
        Deque<Character> operators = new LinkedList<>();

        s = s.trim().replaceAll("\\s+", "");

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int digit = c - '0';
                int j = i + 1;
                for (; j < s.length(); j++) {
                    if (!Character.isDigit(s.charAt(j)))
                        break;
                    digit = digit * 10 + (s.charAt(j) - '0');
                }
                i = j - 1;
                nums.push(digit);
            } else {
                if (c == '+' || c == '-') {
                    while (!operators.isEmpty()) {
                        Character pop = operators.pop();
                        int num1 = nums.pop();
                        int num2 = nums.pop();
                        if (pop == '*') {
                            nums.push(num2 * num1);
                        } else if (pop == '/') {
                            nums.push(num2 / num1);
                        } else if (pop == '-') {
                            nums.push(num2 - num1);
                        } else {
                            nums.push(num2 + num1);
                        }
                    }
                } else {
                    while (!operators.isEmpty() && (operators.peek() == '/' || operators.peek() == '*')) {
                        Character pop = operators.pop();
                        int num1 = nums.pop();
                        int num2 = nums.pop();
                        if (pop == '*') {
                            nums.push(num2 * num1);
                        } else {
                            nums.push(num2 / num1);
                        }
                    }
                }
                operators.push(c);
            }
        }

        while (!operators.isEmpty()) {
            int num1 = nums.pop();
            int num2 = nums.pop();
            Character operator = operators.pop();
            if (operator == '+')
                nums.push(num2 + num1);
            else if (operator == '-')
                nums.push(num2 - num1);
            else if (operator == '*')
                nums.push(num2 * num1);
            else
                nums.push(num2 / num1);
        }

        return nums.pop();
    }
}
